//
// Created by vista on 2017/12/8.
//

#ifndef P_P4_H
#define P_P4_H

#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        auto m = static_cast<int>(nums1.size());
        auto n = static_cast<int>(nums2.size());

        if(m == 0 && n == 0)
        {
            return 0.0;
        }

        auto ptr1 = nums1.begin();
        auto ptr2 = nums2.begin();

        if(m < n) {
            swap(ptr1, ptr2);
            swap(m,n);
        }

        int mid = (m + n) / 2;

        bool odd = ((m+n)&1) == 1;


        int imin = 0,imax = m;
        int i = ( imax + imin - (odd?0:1) ) / 2;

        do{
            int j = mid - (i + 1) ;

            if(!odd){
                j -= 1;
            }

            if(j == -1){

                if( n == 0 ){
                    if( odd )
                        return *(ptr1+i);
                    else
                        return (*(ptr1+i) + *(ptr1+i+1)) / 2.0;

                }else if( *(ptr1+i) <= *ptr2 ){

                    if( odd )
                        return *(ptr1+i);
                    else if(i+1 >= m){
                        return (*(ptr1+i) + *(ptr2)) / 2.0;
                    }else
                        return ( *(ptr1+i)+ std::min( *(ptr2) ,*(ptr1+i+1) )) / 2.0;

                }else{
                    --i;
                    continue;
                }
            }

            if(j == n - 1){
                if( *(ptr2+j) <= *(ptr1+i+1) ){
                    if(odd){
                        return std::max( *(ptr1 + i) , *(ptr2 + j) );
                    } else {
                        return (*(ptr1 + i + 1) + std::max(*(ptr1+i),*(ptr2+j)) )/2.0;
                    }
                }
            }

            if( i == m - 1 && j > -2){
                if( *(ptr1+m-1) <= *ptr2 ) {
                    return *(ptr1 + i);
                } else{
                    --i;
                    continue;
                }
            }
            if( i >=0 && i < m - 1 && j >=0 && j < n - 1 && *(ptr1+i) <= *(ptr2+j+1) && *(ptr2+j)  <= *(ptr1+i+1) )
            {
                if(odd){
                    return std::max(*(ptr1+i),*(ptr2+j));
                }else{
                    return (std::max(*(ptr1+i),*(ptr2+j)) + std::min(*(ptr1+i+1),*(ptr2+j+1)))/2.0;
                }
            }else if(j < -1 || ( j <= n - 1 && *(ptr1+i) > *(ptr2+j+1) ) )
            {
                imax = i;
                i = ( imax + imin/* - (odd?0:1) */) / 2;
                if(imax == i)
                    --i;
            }else if( j > n - 1 || (j >= 0 && *(ptr2+j) > *(ptr1+i+1) ) ){
                imin = i+1;
                i = ( imax + imin /*- (odd?0:1) */) / 2;
                if(imin == i)
                    ++i;
            }
        }while (true);
    }
};

#endif //P_P4_H
